package question6_10;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @description:
 * 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
 * 输入
 * {67,0,24,58}
 * 返回值
 * [58,24,0,67]
 * @author: jhy
 * @time: 2021/5/19 11:09
 */
public class Question6 {


    //方法1：从头到尾遍历链表，使用ArrayList的头插方式，即可逆序打印
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        //参数校验
        if(listNode == null){
            return new ArrayList<>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (listNode != null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }

    //方法2：要求第一个遍历到的节点最后输出，最后一个遍历到的节点第一输出====>后进先出  栈
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {

        if(listNode == null){
            return new ArrayList<>();
        }
        Stack<Integer> stack = new Stack<>();
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }


    //方法3：既然想到了用栈来实现这个函数，而递归本质就是一个栈结构，于是可以想到递归
    //递归方式：我们每次访问一个节点的时候，先递归输出他后面的节点，然后才输出该节点自身
    ArrayList list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }


}
